'''
https://leetcode.cn/problems/number-of-provinces/description/?envType=study-plan-v2&envId=graph-theory
'''
from typing import List


class UF:
    def __init__(self, n):
        self.father = [i for i in range(n)]
        self.sets = n
    def find(self, i):
        if self.father[i] != i:
            self.father[i] = self.find(self.father[i])
        return self.father[i]
    def union(self, i, j):
        fi, fj = self.find(i), self.find(j)
        if fi == fj: return
        self.sets -= 1
        self.father[fi] = fj

class Solution:
    # 并查集
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        uf = UF(n)
        for i in range(n):
            for j in range(i+1, n):
                if isConnected[i][j] == 1:
                    uf.union(i, j)
        return uf.sets

    # bfs
    def findCircleNum2(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n
        q = []
        groups = 0
        for i in range(n):
            if not visited[i]:
                q.append(i)
                while q:
                    u = q.pop()
                    if visited[u]: continue
                    visited[u] = True
                    for v, is_conn in enumerate(isConnected[u]):
                        if is_conn:
                            q.append(v)
                groups += 1
        return groups

    # dfs
    def findCircleNum3(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n
        def dfs(u):
            if visited[u]: return
            visited[u] = True
            for v, is_conn in enumerate(isConnected[u]):
                if is_conn:
                    dfs(v)
        groups = 0
        for u in range(n):
            if not visited[u]:
                dfs(u)
                groups += 1
        return groups



isConnected = [[1,1,1],[1,1,1],[1,1,1]]
print(Solution().findCircleNum(isConnected))